#define _CRT_SECURE_NO_WARNINGS 1
#include <vector>
using namespace std;
class Solution {
public:
    int firstMissingPositive(vector<int>& nums)
    {
        int n = nums.size();
        nums.push_back(nums[0]);
        nums[0] = 0;
        int count = 0;
        for (int i = 1;i < nums.size();)
        {
            if (nums[i] != i)
            {
                if (nums[i] <= 0 || nums[i] > n)
                {
                    nums[i] = 0;
                    ++i;
                }
                else if (nums[nums[i]] != nums[i])
                {
                    swap(nums[i], nums[nums[i]]);
                }
                else
                {
                    nums[i] = 0;
                }
            }
            else
            {
                ++count;
                ++i;
            }
        }
        if (count == n) return n + 1;
        for (int i = 1;i < nums.size();++i)
        {
            if (nums[i] != i)
            {
                return i;
            }
        }
        return 1899;
    }
};